/**
 * @author dx
 * @version 1.0
 * @date 2022/5/24 11:04
 * @description: 力扣 75 颜色分类
 */
public class SortColor {
    public static void main(String[] args) {
        int []test = {0,1,2,2,0,1};
        new SortColor_Solution().sortColors1(test);
        for(int x:test){
            System.out.println(x);
        }
        System.out.println("----------");
        new SortColor_Solution().sortColors2(test);
        for(int x:test){
            System.out.println(x);
        }
    }
}


class SortColor_Solution{
    //冒泡排序方法
    public void sortColors1(int[] nums) {
        int len = nums.length;
        for(int i =len-1;i>0;i--){
            for(int j = 0;j<i;j++){
                if(nums[j+1] < nums[j]){
                    int tem = nums[j+1];
                    nums[j+1] =nums[j];
                    nums[j] = tem;
                }
            }

        }
    }
    //单指针法
    public void sortColors2(int[] nums){
        int pr = 0;
        int n = nums.length;
        for(int i = 0;i < n;i++){
            if(nums[i] == 0){
                int tmp = nums[i];
                nums[i] = nums[pr];
                nums[pr] = tmp;
                pr++;
            }
        }
        int index = pr;
        for(int i = index;i < n;i++){
            if(nums[i] == 1){
                int tmp = nums[i];
                nums[i] = nums[pr];
                nums[pr] = tmp;
                pr++;
            }
        }
    }
    //双指针
    public void sortColors3(int[] nums){
        int p0 = 0,p1 = 1;
        int n = nums.length;
        for(int i= 0;i < n;i++){  //为什么两个都移动(p0,p1),p0:下一个0的位置肯定要移动，p1:当本来p0和p1就在同一个位置时，P1肯定要增加，当不在同一个位置时，p0占了p1一个位置，也要增加
            if(nums[i] == 0){
                int tmp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = tmp;
                if(p1 > p0){
                    tmp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = tmp;
                }
                p0++;
                p1++;
            }
            else if(nums[i] == 1){   //p0不移动，p0不移动，理解为 当前0的位置该是几了
                int tmp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = tmp;
                p1++;
            }
        }
    }
}